/*
 * SudokuSolver.cpp
 *
 *  Created on: Sep 28, 2009
 *      Author: Cha
 */
#include "SudokuSolver.h"
#include "Sudoku.h"
#include <cstdlib>
#include <iostream>

//standard sudoku board 9x9
#define DIMEN 9
#define TOTAL_GRIDS DIMEN*DIMEN

//used to calculate the midpoint of each major grid
#define MAJOR_DIMEN 3
#define FIRST_MID_IDX 10
#define MAJOR_ROW_INCR 17
#define MAJOR_COL_INCR 3

using namespace std;


SudokuSolver::SudokuSolver(int difficulty){
	/*initialize the adj_list*/
	cout << "Loading Board...";
	adj_list = new gridHolder*[TOTAL_GRIDS];
	game = Sudoku();
	game.initGame(difficulty);

	/*set the DFS stack to NULL*/
	stack_top = NULL;
	/*set the front of the AC queue to NULL*/
	queue_front = NULL;

	cout << "done\n";
}

/*initializes the elements of the adj_list, which will serve as the head element
 * for their list of neighbors
 */
void SudokuSolver::initAdjList(){
	cout << "Initializing Adjacency Array...done\n";
	for(int idx = 0; idx < TOTAL_GRIDS; idx++){
		gridHolder *new_elem = (gridHolder *)malloc(sizeof(struct gridHolder));
		initAdjListElem(new_elem, idx);
		adj_list[idx] = new_elem;
	}
	findNeighbors();

}

void SudokuSolver::initAdjListElem(gridHolder *cur, int index){
	cur->next = NULL;
	cur->prev = NULL;
	cur->space = game.getGrid(index);
}

/*finds(calculates) the neighbors for each element in the adj_list. Neighbors
 * are other sudokuGrids that are effected by any change to the sudokuGrid
 * stored in current adj_list element. Each element in the adj_list will have
 * 20 neighbors.
 */
void SudokuSolver::findNeighbors(){
	cout << "Populating Adjacency List...";
	int element_index, minor_row, minor_col, major_row, major_col, major_center;
	gridHolder *new_elem;
	for(int i = 0; i < TOTAL_GRIDS; i++){
		/*first we need to covert a 1-d index value into row and col values for a 2-d board.
		 *see documentation for further explanations about each variable*/
		element_index = (adj_list[i]->space)->board_index;
		minor_row = element_index / DIMEN;
		minor_col = element_index % DIMEN;
		//cout << element_index << " " << minor_row << " " << minor_col << "\n";
		/*find the 1-d indices of row neighbors using 2-d row value, and add these
		 * neighbors to the adj_list*/
		for(int idx = (minor_row * DIMEN); idx < (minor_row * DIMEN) + DIMEN; idx++){
			new_elem = (gridHolder *)malloc(sizeof(struct gridHolder));
			initAdjListElem(new_elem, idx);
			addNeighbor(adj_list[i], new_elem);
		}

		/* do the same for neighbors in the same column */
		for(int idx = minor_col; idx < TOTAL_GRIDS; idx += DIMEN){
			new_elem = (gridHolder *)malloc(sizeof(struct gridHolder));
			initAdjListElem(new_elem, idx);
			addNeighbor(adj_list[i], new_elem);
		}

		/* now we have to find all the neighbors in the same major grid, first thing is to
		 * calculate the major row and major col values from the minor row and minor col
		 * values. see documentation for explanation of each variable */
		major_row = minor_row / MAJOR_DIMEN;
		major_col = minor_col / MAJOR_DIMEN;

		/* calculate the 1-d index of the element in the center of the major
		 * grid that major_row and major_col fall in.
		 */
		major_center = (((major_row + 1)  * FIRST_MID_IDX) + (major_row * MAJOR_ROW_INCR)) + (major_col * MAJOR_COL_INCR);

		/*now that we know the center, the neighbors are just the 8 sudokuGrids around it*/
		new_elem = (gridHolder *)malloc(sizeof(struct gridHolder));
		initAdjListElem(new_elem, major_center);		//center
		addNeighbor(adj_list[i], new_elem);

		new_elem = (gridHolder *)malloc(sizeof(struct gridHolder));
		initAdjListElem(new_elem, major_center - 10);	//top left
		addNeighbor(adj_list[i], new_elem);

		new_elem = (gridHolder *)malloc(sizeof(struct gridHolder));
		initAdjListElem(new_elem, major_center - 9);	//top
		addNeighbor(adj_list[i], new_elem);

		new_elem = (gridHolder *)malloc(sizeof(struct gridHolder));
		initAdjListElem(new_elem, major_center - 8);	//top right
		addNeighbor(adj_list[i], new_elem);

		new_elem = (gridHolder *)malloc(sizeof(struct gridHolder));
		initAdjListElem(new_elem, major_center - 1);	//left
		addNeighbor(adj_list[i], new_elem);

		new_elem = (gridHolder *)malloc(sizeof(struct gridHolder));
		initAdjListElem(new_elem, major_center + 1);	//right
		addNeighbor(adj_list[i], new_elem);

		new_elem = (gridHolder *)malloc(sizeof(struct gridHolder));
		initAdjListElem(new_elem, major_center + 8);	//bottom left
		addNeighbor(adj_list[i], new_elem);

		new_elem = (gridHolder *)malloc(sizeof(struct gridHolder));
		initAdjListElem(new_elem, major_center + 9);	//bottom
		addNeighbor(adj_list[i], new_elem);

		new_elem = (gridHolder *)malloc(sizeof(struct gridHolder));
		initAdjListElem(new_elem, major_center + 10);	//bottom right
		addNeighbor(adj_list[i], new_elem);
	}
	cout << "done\n";
}

void SudokuSolver::addNeighbor(gridHolder *head, gridHolder *elem){
	gridHolder *iter = head;
	bool found = false;

	//this will check head against elem, in the case that head is the
	//only item in the list.
	if((iter->space)->board_index == (elem->space)->board_index)
		found = true;

	while(iter->next != NULL && !found){
		//check for duplicates
		if((iter->space)->board_index == (elem->space)->board_index)
			found = true;
		iter = iter->next;
	}
	if(!found){
		iter->next = elem;
		elem->prev = iter;
	}
}

/*check if all the grids are filled out with valid values*/
bool SudokuSolver::isGameSolved(){
	for(int i = 0; i < TOTAL_GRIDS; i++){
		if((adj_list[i]->space)->actual_value == -1)
			return false;
		else if(!allDiff(adj_list[i], (adj_list[i]->space)->actual_value))
			return false;
	}
	return true;
}

void SudokuSolver::printAdjList(){
	for(int x = 0; x < TOTAL_GRIDS; x++){
		gridHolder *iter;
		cout << "Root Grid Index: " << x << "\n";
		cout << "Neighbors: ";
		iter = adj_list[x];
		while(iter != NULL){
			cout << (iter->space)->board_index << " ";
			iter = iter->next;
		}
		cout << "\n\n";
	}
}

void SudokuSolver::printBoardState(){
	for(int x = 0; x < TOTAL_GRIDS; x++){
		cout <<(adj_list[x]->space)->actual_value << " ";
		if((x + 1) % 9 == 0)
			cout << "\n";
	}
}

/******************************************************************************
 * Functions to carry out DFS on a sudoku board
 * mode determines what algorithms are used.
 * 0 = DFS only
 * 1 = + allDiff		<-- default should be at least 1, dunno if you want brute force unless 99% of the sudoku board is filled already
 * 2 = + forward checking
 * 3 = + Arc Consistency
 */
void SudokuSolver::DFSSolver(int mode){
	bool valid = true;
	long int iter_count = 0, backtrack_count = 0;
	gridHolder *cur_grid = getUnfilledGrid();
	int first = (cur_grid->space)->board_index;
	while(true){
		/*every grid has been filled*/
		if(cur_grid == NULL){
			if(isGameSolved())
				break;
			else	{		
				cur_grid = popStack(); //backtrack!
				backtrack_count++;
				int wrong_pathval = (cur_grid->space)->actual_value;
				game.purgeValue(cur_grid->space, wrong_pathval); //block that path
				game.setGridValue(cur_grid->space, -1);
			}
		}
		else{
			int fill_val = game.getNextPossibleValue(cur_grid->space);
			if(fill_val != -1){
			   	if(mode >= 1)
					valid = allDiff(cur_grid, fill_val);
				if(valid){
					game.setGridValue(cur_grid->space, fill_val);
					pushStack(cur_grid); 				//put this grid on the stack
					//if(mode >= 2)					//FC not debugged
						//forwardCheck(cur_grid);
					cur_grid = getUnfilledGrid();
				}
				else{
					game.purgeValue(cur_grid->space, fill_val);
				}
			}
			//if the current grid has no more possible values, backtrack to previous grid. Once at the previous grid, block
			//the path you just came from
			else{
				game.restorePossibleValues(cur_grid->space);
				if((cur_grid->space)->board_index != first){
					game.setGridValue(cur_grid->space, -1);
					cur_grid = popStack(); //backtrack!
					backtrack_count++;
					int wrong_pathval = (cur_grid->space)->actual_value;
					game.purgeValue(cur_grid->space, wrong_pathval); //block that path
				}
				else{
					int test = (cur_grid->space)->actual_value;
					for(int i = 1; i <= test; i++)
						game.purgeValue(cur_grid->space, i);
				}
			}
		}
		iter_count++;
	}
	cout << "Paths Walked(including backtracking): " << iter_count << " Backtracks: " << backtrack_count << endl;
}



/******************************************************************************
 * Function to carry out forwardchecking on the sudoku board
 */
void SudokuSolver:: forwardCheck(gridHolder *elem){
	gridHolder *cur = elem; 
	int val_to_purge = (cur->space)->actual_value;
	//purge all neighbors
	cout << "purging " << val_to_purge << " from neighbors of: " << cur->space->board_index << endl;
	while(cur != NULL){
		game.purgeValue(cur->space, val_to_purge);
		cur = cur->next;
	}
}

void SudokuSolver::restoreNeighbors(gridHolder *elem, int res_val){
	gridHolder *iter = elem->next;
	while(iter != NULL){
		game.restoreValue(iter->space, res_val);
		iter = iter->next;
	}
}

gridHolder* SudokuSolver::getUnfilledGrid(){
	/*just run through the head elements of the adj_list and return the first
	unfilled sudoku grid.*/
	for(int i = 0; i < TOTAL_GRIDS; i++){
		if((adj_list[i]->space)->actual_value == -1)
			return adj_list[i];
	}
	return NULL;
}

bool SudokuSolver::allDiff(gridHolder *suspect, int grid_val){
	/*run through all its neighbors and make sure they do not have the
	  the same value*/
	gridHolder *iter = suspect->next;
	while(iter != NULL){
		if((iter->space)->actual_value == grid_val)
			return false;
		iter = iter->next;
	}
	return true;
}



/******************************************************************************
 * Stack management stuff for DFS.
 */
bool SudokuSolver::stackIsEmpty(){
	if(stack_top == NULL)
		return true;
	return false;
}

void SudokuSolver::pushStack(gridHolder *cur_grid){
	DataStructElem *new_elem = (DataStructElem *)malloc(sizeof(struct DataStructElem));
	new_elem->grid = cur_grid;
	new_elem->prev = NULL;
	new_elem->next = NULL;
	if(stack_top == NULL){
		stack_top = new_elem;
	}
	else{
		stack_top->next = new_elem;
		new_elem->prev = stack_top;
		stack_top = stack_top->next;
	}
}

gridHolder* SudokuSolver::popStack(){
	DataStructElem *top = stack_top;
	gridHolder *temp;
	stack_top = stack_top->prev;
	if(stack_top != NULL){
		(stack_top->next)->prev = NULL;
		stack_top->next = NULL;
	}
	temp = top->grid;
	delete(top);
	return temp;
}

void SudokuSolver::printStack(){
	DataStructElem *iter = stack_top;
	cout << "Stack Contents: ";
	while(iter != NULL){
		cout << "(" << ((iter->grid)->space)->board_index << "," << ((iter->grid)->space)->actual_value << ") ";
		iter = iter->prev;
	}
	cout << "\n";
}

/******************************************************************************
 * Queue management stuff for Arc Consistancy.
 */
bool SudokuSolver::queueIsEmpty(){
	if(queue_front == NULL)
		return true;
	return false;
}

void SudokuSolver::enqueue(gridHolder *cur_grid){
	DataStructElem *new_elem = (DataStructElem *)malloc(sizeof(struct DataStructElem));
	new_elem->grid = cur_grid;
	new_elem->prev = NULL;
	new_elem->next = NULL;
	if(queue_front == NULL){
		queue_front = new_elem;
	}
	else{
		DataStructElem *iter = queue_front;
		while(iter->next != NULL)
			iter = iter->next;
		iter->next = new_elem;
		new_elem->prev = iter;
	}
}

gridHolder* SudokuSolver::dequeue(){
	DataStructElem *front = queue_front;
	queue_front = queue_front->next;
	

	if(front == NULL)
		cout << "error 121: whoamigod\n";
	
	return front->grid;
}

